The present invention concerns a method of determining a segmentation of a set of coefficients representing at least part of a digital image in order to insert and extract a set of watermarking signals, and an associated method of inserting and extracting these watermarking signals.
Correlatively it concerns a device for determining a segmentation of a set of coefficients representing at least part of a digital image in order to insert and extract a set of watermarking signals and an associated device for inserting and extracting these watermarking signals.
The present invention lies in general terms in the technical field of watermarking of digital images, more particularly fixed images.
Watermarking digital data makes it possible to protect these data, for example by associating copyright information therewith, or conveying added value data, such as metadata.
In its general principle, watermarking consists of inserting an indelible watermark in digital data, similar to the encoding of additional information in the data.
The decoding of this additional information makes it possible, for example, to check the copyright information inserted.
This inserted watermark must consequently be at the same time imperceptible, robust to certain distortions applied to the digital image and capable of reliable detection.
In a conventional fashion, a usual technique of inserting a watermarking signal in a digital image consists of using a modulation model in which at least one subset of coefficients representing the digital image is modulated according to this model using a weighting coefficient.
Denoting a set of coefficients representing at least part of a digital image as X={Xi, 1xe2x89xa6ixe2x89xa6N} and a watermarking signal of size Pxe2x89xa6N as w={wj, 1xe2x89xa6jxe2x89xa6P}, a pseudo-random signal of known distribution and null mean, the insertion formula is:
Xxe2x80x2j=Xj+b.xcex1j.wj with 1xe2x89xa6jxe2x89xa6P,
in which {Xj, 1xe2x89xa6jxe2x89xa6P} is a subset of the set of coefficients X, b is an information bit, and xcex1j is a weighting coefficient, also referred to as modulation amplitude.
Detection of the watermarking signal then consists of detecting whether or not the pseudo-random sequence w has been inserted in a set of coefficients. This detection is carried out without using the original image and can be based on a standardised statistical test which makes it possible to calculate a probability of detection.
Such an insertion technique makes it possible, by inserting a watermarking signal, to insert a single information bit since the response of the detector is binary (yes/no). Typically, in order to insert a binary signal, either b=1 or b=xe2x88x921 is used, depending on whether the value of the bit to be inserted is zero or one.
In order to insert a larger number of information bits in the digital image, in particular when a code of C bits indicating for example the name or address of the owner or author of the image is required, it is necessary to reiterate the insertion method described previously as many times as there are information bits to be inserted.
In other words, it is necessary to choose C subsets of coefficients and effect the modulation of these subsets by choosing C watermarking signals.
Preferably distinct subsets of coefficients are chosen so that the modulations are not superimposed on each other, which could interfere with the detection or cause unwanted visual effects.
It is consequently a question of choosing a partitioning of the coefficients representing the digital image into C distinct subsets, each carrying an information bit.
Methods are known for the arbitrary partitioning of the set of coefficients, into blocks, independently of the content of the digital image.
However, the content of the images is not spatially homogeneous, which gives rise to unequal probabilities of detection for the detected bits, and consequently a probability of global error on the inserted message which cannot be minimal. It is therefore advantageous to determine a partitioning which is adapted to the image. In this case, if it is wished to insert a predetermined number C of watermarking bits, it is also necessary to minimise a probability of error at the time of extraction of the watermarking signals.
The purpose of the present invention is to propose a method of determining a partitioning of the signal to be watermarked, whilst minimising a probability of error in the detection of the predetermined number of watermarking signals.
To this end, the invention proposes a method of determining a segmentation into distinct regions of a set of coefficients representing at least part of an image in order to insert a set of watermarking signals with a predetermined cardinal, characterised in that it includes the steps of:
generating a set of acceptable segmentations,
calculating, for each acceptable segmentation, a probability of error on the detection of the watermarking signals inserted in said each acceptable segmentation, and
selecting a segmentation in the set of acceptable segmentations, by minimising, on all the acceptable segmentations, the probability of error subject to a constraint on the cardinal of the regions of the selected segmentation, with respect to the cardinal of said set of watermarking signals.
It is thus possible to effect a segmentation of a set of coefficients into distinct regions, effecting adaptive partitioning which minimises a probability of error in the detection of the predetermined number of watermarking signals.
According to a preferred characteristic of the invention, said set of coefficients is a set of transformed coefficients issuing from a spatial-frequency transformation of a digital image. This type of transformation is frequently used in image processing.
According to another preferred characteristic of the invention, the acceptable segmentations are obtained by arborescent segmentation of the coefficients representing at least part of an image.
According to a preferred characteristic of the invention, the acceptable segmentations are obtained by segmenting into a quaternary tree the coefficients representing at least part of an image.
This implementation is rapid and has low calculation complexity.
According to a preferred characteristic of the invention, each of the watermarking signals is associated with a watermarking bit and the probability of error on the detection of the watermarking signals is the probability of making at least one error on a bit during the detection of the watermarking bits.
According to a preferred characteristic of the invention, the minimisation of the probability of error includes a maximisation of a separable quantity and the selected segmentation is obtained by pruning an arborescent segmentation.
According to a preferred characteristic of the invention, the constraint of the optimisation step is that the cardinal of the regions of the selected segmentation is greater than or equal to the cardinal of said set of watermarking signals.
According to a preferred characteristic of the invention the method of determining a segmentation comprises a step of applying a distortion to the set of coefficients, before the step of generating a set of acceptable segmentations.
In this embodiment, the method comprises more precisely the steps of:
generation of a centred pseudo-random sequence (w) equal in size to the cardinal number of the said set of coefficients, formed from centred pseudo-random sub-sequences;
modulation) of the said set of coefficients by the said centred pseudo-random sequence in order to insert the same information bit on the said set of coefficients; and
applying a distortion to the set of coefficients, before the step of generating a set of acceptable segmentations.
This embodiment allows to enhance the robustness of an inserted watermark, against some post-processing undergone by the image.
According to a preferred characteristic of the invention, the method also includes the display of the probability of error on all the watermarking signals.
This probability of error indicates the robustness of the insertion of the watermarking signals.
The invention also concerns a method of inserting, in a digital image, watermarking signals respectively associated with watermarking bits, characterised in that it includes a method of determining a segmentation as previously presented, and a step of inserting the watermarking bits by modulation of the coefficients of respective regions of the segmentation.
According to a preferred characteristic of the invention, the regions are considered in a predetermined order during the insertion step.
The invention also relates to a method of extracting from a digital image watermarking signals respectively associated with watermarking bits, characterised in that it includes a step of determining a segmentation as previously presented, and a step of extracting watermarking bits.
Correlatively, the invention relates to a device for determining a segmentation into distinct regions of a set of coefficients representing at least part of an image in order to insert a set of watermarking signals with a predetermined cardinal, characterised in that it has:
means of generating a set of acceptable segmentations,
means of calculating, for each acceptable segmentation, a probability of error on the detection of the watermarking signals inserted in said each acceptable segmentation, and
means of selecting a segmentation in the set of acceptable segmentations, by minimising, on all the acceptable segmentations, the probability of error subject to a constraint on the cardinal of the regions of the selected segmentation, with respect to the cardinal of said set of watermarking signals.
The invention also concerns a device for inserting in a digital image watermarking signals respectively associated with watermarking bits, characterised in that it includes a device for determining a segmentation as previously presented, and means of inserting watermarking bits by modulating the coefficients of respective regions of the segmentation.
According to a preferred characteristic of the invention, the insertion means are adapted to consider the regions in a predetermined order.
The invention also concerns a device for extracting, from a digital image, watermarking signals respectively associated with watermarking bits, characterised in that it includes a device for determining a segmentation as previously presented, and means of extracting watermarking bits.
The determination, insertion and extraction devices have means for implementing the characteristics previously presented.
The present invention also concerns a computer, a digital image processing apparatus, a digital printer, a scanner, a digital photographic apparatus and a digital camera adapted to implement the method of determining a partitioning and the insertion method according to the invention and/or comprising a device for determining a partitioning or an insertion device according to the invention.
These devices for determining a partitioning, for inserting and for extracting, this computer, this scanner, this digital photographic apparatus and this digital camera have characteristics and advantages similar to those described with reference to the methods of determining a partitioning and inserting which they implement.
A storage means or information carrier, which can be read by a computer or a microprocessor, incorporated or not into the latter, possibly removable, comprises portions of software codes or program instructions adapted to implement the steps of the method of determining a partitioning or insertion according to the invention, when said storage means or information carrier is implemented by a microprocessor or computer.